package www.study.com;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

//串联所有单词的子串 https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
public class code30 {
    public static void main(String[] args) {

    }

    class Solution {
        //方法二：分组求解法
        public List<Integer> findSubstring(String s, String[] words) {
            //分组
            List<Integer> res = new ArrayList<>();
            HashMap<String,Integer> wordsMap = new HashMap<>();
            for(String word : words){
                wordsMap.put(word,wordsMap.containsKey(word) ? wordsMap.get(word) + 1 : 1);
            }
            int wordLength = words[0].length();
            for(int i = 0 ; i < wordLength ; i++){ //分组
                HashMap<String,Integer> curMap = new HashMap<>();
                for(int j = i ; j <= s.length() - wordLength ; j+= wordLength){
                    String nowS = s.substring(j,j + wordLength);
                    curMap.put(nowS,curMap.containsKey(nowS) ? curMap.get(nowS) + 1 : 1);
                    if(j >= i + wordLength * words.length){
                        int topP = j - wordLength * words.length;
                        String delS = s.substring(topP,topP + wordLength);
                        curMap.put(delS,curMap.get(delS) - 1);
                        if(curMap.get(delS) == 0){
                            curMap.remove(delS);
                        }
                    }
                    if(wordsMap.equals(curMap)){
                        res.add(j - (words.length - 1) * wordLength);
                    }
                }
            }
            return res;
        }

        //方法一：暴力解法，可通过用例
        // public List<Integer> findSubstring(String s, String[] words) {
        //     List<Integer> res = new ArrayList<>();
        //     HashMap<String, Integer> wordMap = new HashMap<>();
        //     int wordLength = words[0].length() * words.length;
        //     int singleLength = words[0].length();
        //     for(String word : words){
        //         wordMap.put(word,wordMap.containsKey(word) ? wordMap.get(word) + 1 : 1);
        //     }
        //     for(int i = 0 ; i <= s.length() - wordLength ; i++){
        //         String cur = s.substring(i,i + wordLength);
        //         //System.out.println("outer : " + cur);
        //         HashMap<String,Integer> curMap = new HashMap<>();
        //         for(int j = 0 ; j <= wordLength - singleLength ; j += singleLength){
        //             String cur_s = cur.substring(j,j + singleLength);
        //             //System.out.println("inner : " + cur_s);
        //             if(!wordMap.containsKey(cur_s)) break;
        //             curMap.put(cur_s,curMap.containsKey(cur_s) ? curMap.get(cur_s) + 1 : 1);
        //         }
        //         if(curMap.equals(wordMap)){
        //             res.add(i);
        //         }
        //     }
        //     return res;
        // }
    }
}
